#pragma once

template<typename T>
class CLinkedQueue
{
private:
    struct Node {
        Node(Node* pPrev = nullptr, Node* pNext = nullptr)
            : m_pNext(pNext), m_pPrev(pPrev)
        {
        }

        Node(T data, Node* pPrev = nullptr, Node* pNext = nullptr)
            :m_data(data), m_pNext(pNext), m_pPrev(pPrev)
        {
        }

        T m_data;
        Node* m_pPrev;
        Node* m_pNext;
    };

public:
    CLinkedQueue()
    {
        m_pHead = new Node();
        m_pTail = new Node();
        m_pHead->m_pNext = m_pTail;
        m_pTail->m_pPrev = m_pHead;
        m_nSize = 0;
    }
    ~CLinkedQueue()
    {
        clear();
        delete m_pHead;
        delete m_pTail;
    }

    void push(const T& elem)
    {
        Node* p = new Node(elem, m_pTail->m_pPrev, m_pTail);
        m_pTail->m_pPrev->m_pNext = p;
        m_pTail->m_pPrev = p;
        m_nSize++;
    }

    void pop()
    {
        Node* pDel = m_pHead->m_pNext;
        m_pHead->m_pNext = pDel->m_pNext;
        pDel->m_pNext->m_pPrev = m_pHead;
        delete pDel;
        m_nSize--;
    }

    T peek() const
    {
        return m_pHead->m_pNext->m_data;
    }

    bool empty() const
    {
        return m_nSize == 0;
    }

    void clear()
    {
        Node* pDel = m_pHead->m_pNext;
        while (pDel != m_pTail)
        {
            Node* pNext = pDel->m_pNext;
            delete pDel;
            pDel = pNext;
        }
        m_pHead->m_pNext= m_pTail;
        m_pTail->m_pPrev = m_pHead;
    }
private:
    Node* m_pHead;
    Node* m_pTail;
    int m_nSize;
};


template<typename T>
class CArrayQueue
{
private:
    struct Node {
        Node(Node* pNext = nullptr)
            : m_pNext(pNext)
        {
        }

        Node(T data, Node* pNext = nullptr)
            :m_data(data), m_pNext(pNext)
        {
        }

        T m_data;
        Node* m_pNext;
    };

public:
    CArrayQueue(int nSize = 1)
    {
        m_pBuf = m_pFront = new T[nSize];
        m_nSize = 0;
    }
    ~CArrayQueue()
    {
        delete[] m_pBuf;
    }

    void push(const T& elem)
    {
        m_pFront[m_nSize++] = elem;
    }

    void pop()
    {
        m_pFront++;
        m_nSize--;
    }

    T peek() const
    {
        return *m_pFront;
    }

    bool empty() const
    {
        return m_nSize == 0;
    }

    int size() const
    {
        return m_nSize;
    }

    void clear()
    {
        m_pFront = m_pBuf;
        m_nSize = 0;
    }
private:
    T* m_pBuf;
    T* m_pFront;
    int m_nSize;
};

